package 二叉树链表实现;

import java.util.LinkedList;
import java.util.Stack;

public class BinaryTreeByLink {
    public TreeNode root;
    //添加节点
    public void add(int data){
        TreeNode newNode=new TreeNode(data);
        //建立树根
        if(root==null){
            root=newNode;
            return;
        }
        TreeNode cur=root;
        while(true){
            if(newNode.value<cur.value){
                if(cur.left==null){
                    cur.left=newNode;
                    return;
                }else{
                    cur=cur.left;
                }
            }else{
                if(cur.right==null){
                    cur.right=newNode;
                    return;
                }else{
                    cur=cur.right;
                }
            }
        }
    }
    //二叉树的遍历

    //前序遍历
    public void preOrder1(TreeNode root){
        if(root!=null){
            System.out.print(root.value+" ");
            preOrder1(root.left);
            preOrder1(root.right);
        }
    }
    //前序遍历非递归1
    public void preOrder2(TreeNode cur){

        Stack<TreeNode> stack=new Stack<>();
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.add(cur);
                System.out.print(cur.value+" ");
                cur=cur.left;
            }
            cur=stack.pop();
            cur=cur.right;
        }
    }
    //前序遍历非递归2
    public void preOrder3(TreeNode cur){
        Stack<TreeNode> stack=new Stack<>();
        stack.add(cur);
        while(!stack.isEmpty()){
            cur=stack.pop();
            System.out.print(cur.value+" ");
            if(cur.right!=null)
                stack.add(cur.right);
            if(cur.left!=null)
                stack.add(cur.left);
        }
    }
    //中序遍历
    public void inOrder1(TreeNode root){
        if(root!=null){
            inOrder1(root.left);
            System.out.print(root.value+" ");
            inOrder1(root.right);
        }
    }
    //中序遍历非递归
    public void inOrder2(TreeNode cur){
        Stack<TreeNode> stack=new Stack<>();
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.add(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            System.out.print(cur.value+" ");
            cur=cur.right;
        }
    }
    //后序遍历
    public void postOrder1(TreeNode root){
        if(root!=null){
            postOrder1(root.left);
            postOrder1(root.right);
            System.out.print(root.value+" ");
        }
    }
    //后序遍历非递归
    public void postOrder2(TreeNode cur){
        if(cur==null)
            return;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode pre=null;
        stack.add(cur);
        while(!stack.isEmpty()){
            cur=stack.peek();
            if((cur.left==null&&cur.right==null)||(pre!=null&&(pre==cur.left||pre==cur.right))){
                System.out.print(cur.value+" ");
                stack.pop();
                pre=cur;
            }else{
                if(cur.right!=null)
                    stack.add(cur.right);
                if(cur.left!=null)
                    stack.add(cur.left);
            }
        }
    }
    //层序遍历非递归
    public void levelOrder(TreeNode cur){
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(cur);
        while(!queue.isEmpty()){
            cur=queue.pop();
            System.out.print(cur.value+" ");
            if(cur.left!=null)
                queue.add(cur.left);
            if(cur.right!=null)
                queue.add(cur.right);
        }
    }
}
